package lss

import C "gitee.com/ljfirst/algo-go-sdk/common/constant"

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/7/10 02:15
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description
 **/
type LSS_Dynamic struct {
	Sum      int   //最大子段和
	Sequence []int //最大子段和序列
}

func (m *LSS_Dynamic) Method(array []int) {
	m.Sequence = make([]int, 0)
	m.Sum = 0
	if len(array) == 0 {
		return
	}
	temp := 0
	begin := 0
	for k, v := range array {
		temp += v
		if temp < v {
			temp = v
			begin = k
		}
		if temp > m.Sum {
			m.Sum = temp
			m.Sequence = array[begin : k+1]
		}
	}
}

func (m *LSS_Dynamic) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.LSS, C.Dynamic},
		Desc: &C.Desc{
			Name:   "LSS_Dynamic",
			NameCn: "最大子段和:动态规划",
			ParamsDesc: map[string]string{
			},
			Example: map[int]string{
			},
		},
	}
}
